#include "BtreePlus.h"
#include <sstream>
#include "common.h"
#include "Pager.h"
#include "BtreePlusNodeView.h"
#include "BtreePlusPageNumberAllocator.h"
#include "Page.h"


using namespace std;
BtreePlus::BtreePlus(const std::string & name)
: fileName(name+".db")
, allocator(new BtreePlusPageNumberAllocator())
, root(nullptr)
, pager(nullptr)
{
    pager = new Pager(fileName.c_str(), 0x400*0x80, 0x80);
}
BtreePlus::~BtreePlus(){
    if(pager != nullptr){
        delete pager;
        pager = nullptr;
    }

    if(allocator != nullptr){
        delete allocator;
        allocator = nullptr;
    }
    root = nullptr;
}
// Current Function:
//      open, alloc page for root, and to commit  when close btree;
// NOTE: doesn't read Page from file
int BtreePlus::open(){
    int ret = pager->open();
    if(ret != 0) return ret;

    //root = IBtreePlusNodeView::CreateInterior(this->allocPage()); //for memroy mode
    root = IBtreePlusNodeView::CreateLeaf(this->allocPage()); //for memroy mode
    if(root == nullptr) 
        return -1; //No memory
    return 0;
}

int BtreePlus::close(){
    //write Root Page
    int ret = writePage(root->getPage());
    if(ret != 0) return ret;

    //commit all change
    ret = commit();
    if(ret != 0) return ret;

    delete root;
    root = nullptr;

    pager->close();
    return 0;
}



int BtreePlus::_split(BtreePlusInteriorNodeView * node, IBtreePlusNodeView * sub, int index){
    assert(node->isInterior());
    assert((node->getTotal() - node->getUsed()) >= 1);//assert by insertNoFull
    assert(index >= 0);

    if(sub->isLeaf()){
        BtreePlusLeafNodeView * y = (BtreePlusLeafNodeView*)sub;
        Page * page = allocPage(); assert(page != nullptr);
        shared_ptr<BtreePlusLeafNodeView> z(IBtreePlusNodeView::CreateLeaf(page));

        //move [t, 2t-1] => z[0, t-1]
        for(int i = y->getDegree(), used = y->getUsed(); i < used; ++i){
            z->append(y->getKey(i), y->getValue(i));
        }
        y->usedRef() -= y->getDegree(); //del y[t,2t-1]
        
        assert(0 == node->insert(index+1, z->getKey(0), z->getPageNo()));
        z->setParent(node->getPageNo());

        z->setNext(y->getNext());
        y->setNext(z->getPageNo());
        return 0;
    }
    else{
        BtreePlusInteriorNodeView * y = (BtreePlusInteriorNodeView*)sub;
        Page * page = allocPage(); assert(page != nullptr);
        shared_ptr<BtreePlusInteriorNodeView> z(IBtreePlusNodeView::CreateInterior(page));

        for(int i = y->getDegree(), used = y->getUsed(); i < used; ++i){
            z->append(y->getKey(i), y->getChild(i));
        }
        y->usedRef() -= y->getDegree();

        assert(0 == node->insert(index + 1, z->getKey(0), z->getPageNo()));
        z->setParent(node->getPageNo());
        return 0;
    }
}
static int _findInsertToChildIndex(BtreePlusInteriorNodeView * interior, const RowIDType key){
    int i = 0; 
    int used = interior->getUsed();
    assert(used > 0);
    for(; i < used; ++i){
        auto i_key = interior->getKey(i);
        if(key > i_key){
            continue;
        }
        else if(key < i_key){
            break;
        }
        else 
            return -1; //Duplicated Key
    }
    return (i == 0) ? i : i -1; //[0, used-1]
}

int BtreePlus::_insertNoFull(IBtreePlusNodeView * node, const RowIDType key, const std::string & value){
    if( node->isLeaf()){
        BtreePlusLeafNodeView * leaf = (BtreePlusLeafNodeView*)node;
        if(leaf->insert(key, value) != 0) return -1; // insert Failed

        //insert the header of leaf
        if(leaf->getKey(0) == key){
            PageNumberType  parent = leaf->getParent();
            while(parent != 0){
                shared_ptr<BtreePlusInteriorNodeView> cur(IBtreePlusNodeView::LoadInterior(pager->acquirePage(parent)));
                assert(key < cur->getKey(0));
                cur->setKey(0, key);
                parent = cur->getParent();
            }
        }
        return 0;
    }
    //isInterior
    BtreePlusInteriorNodeView * interior = (BtreePlusInteriorNodeView*)node;

    int index = _findInsertToChildIndex(interior, key);//find proper child index for inserting
    if(index == -1) return -1; //Duplicated Key

    shared_ptr<IBtreePlusNodeView> childNv(IBtreePlusNodeView::Load(pager->acquirePage(interior->getChild(index))));
    if(childNv->isFull()){
        if(0 != _split(interior, childNv.get(), index)){
            return -1; // split failed
        }
        if(key > node->getKey(index)){
            shared_ptr<IBtreePlusNodeView> rightNv(IBtreePlusNodeView::Load(pager->acquirePage(interior->getChild(index + 1))));
            assert(0 == _insertNoFull(rightNv.get(), key, value));
            return 0;
        }
    }
    assert(0 == _insertNoFull(childNv.get(), key, value));
    return 0;
}

int BtreePlus::insert(const RowIDType key, const std::string & value){
    if(root->isFull()){
        Page * page = allocPage(); assert(page != nullptr);
        BtreePlusInteriorNodeView * newRoot = IBtreePlusNodeView::CreateInterior(page);
        IBtreePlusNodeView * sub = root;

        //2. set proper  relation  newRoot[0]->sub
        newRoot->append(sub->getKey(0), sub->getPageNo());
        sub->setParent(newRoot->getPageNo());

        //3. split(newRoot, sub)
        _split(newRoot, sub, 0);
        root = newRoot;
        delete sub; //free BtreePlusNodeView object of Old root

        return _insertNoFull(root, key, value);
    }
    else{
        return _insertNoFull(root, key, value);
    }
    return 0;
}

int BtreePlus::del(const RowIDType key){
    //TODO:
    return 0;
}


int BtreePlus::_find(PageNumberType pageNo, const RowIDType key, std::string & data) const{
    auto page = pager->allocPage(pageNo);
    shared_ptr<IBtreePlusNodeView> nv(IBtreePlusNodeView::Load(page));
    assert(nv != nullptr);
    if(nv->isLeaf()){
        int i = 0;
        int used = nv->getUsed();
        for(; i < used; ++i){
            RowIDType ik = nv->getKey(i);
            if( key > ik){
                continue; 
            }
            else if(key == ik){
                data = ((BtreePlusLeafNodeView*)nv.get())->getValue(i);
                return 0;
            }
            else{ // key < ik
                return -1;
            }
        }
        if( i == used){
            return -1;
        }
    }
    else{ 
        assert(nv->getUsed() > 0);//nv->isInterior

        int i = 0; 
        int used = nv->getUsed();
        for(; i < used; ++i){
            RowIDType ik = nv->getKey(i);
            if(key > ik){
                continue;
            }
            else if(key == ik){
                auto child = ((BtreePlusInteriorNodeView*)nv.get())->getChild(i);
                return _find(child, key, data);
            }
            else{ // key < ik;
                if( i > 0){
                    auto child = ((BtreePlusInteriorNodeView*)nv.get())->getChild(i-1);
                    return _find(child, key, data);
                }
                // i == 0 && key < ik;
                return -1;
            }
        }
        if(i > 0 && i == used){
            auto child = ((BtreePlusInteriorNodeView*)nv.get())->getChild(i-1);
            return _find(child, key, data);
        }
        return -2; // i ==0 && nv->isInterior ??? Error
    }
    return 0;
}

int BtreePlus::find(const RowIDType key, std::string & data) const{
    //return "{\"orderId\":1,\"orderNo\":\"000001\",\"price\":257.800000}";
    assert(root != nullptr);
    return _find(root->getPageNo(), key, data);
}





std::string BtreePlus::toString(){
    std::ostringstream oss;
    oss << "fileName:[" << fileName  << "]" << std::endl;

    assert(root != nullptr && root->getPage() != nullptr);

    lvQueue.push_back(root);
    lvQueue.push_back(nullptr);
    _layerPrint(oss);
    return  oss.str();
}

void BtreePlus::_layerPrint(std::ostream & os) {
    while(!lvQueue.empty()){
        auto nv = lvQueue.front();
        lvQueue.pop_front();
        if(nv != nullptr){
            os << " NO:" << nv->getPageNo()
                //<< ",tp:"  << nv->getType() 
                //<< ",used:" << nv->getUsed() 
                //<< ",deg:" << nv->getDegree()
                //<< ",full:" << nv->getTotal()
                //<< ",p:" << nv->getParent() 
                //<< ",next:" << (nv->isLeaf()? ((BtreePlusLeafNodeView*)nv)->getNext(): -1)
                ;
            for(int i = 0, used = nv->getUsed(); i < used; ++i){
                if(nv->isLeaf()){
                    os << " ##k:[" << nv->getKey(i) <<  "],v:(" << ((BtreePlusLeafNodeView*)nv)->getValue(i) << ")";
                }
                else{
                    PageNumberType childPageNo = ((BtreePlusInteriorNodeView*)nv)->getChild(i);
                    os << " ##k:[" << nv->getKey(i) << "],c:" << childPageNo << "";

                    Page * child = pager->acquirePage(childPageNo);
                    assert(child != nullptr);

                    IBtreePlusNodeView * childNv = IBtreePlusNodeView::Load(child);
                    assert(childNv != nullptr);

                    lvQueue.push_back(childNv);
                }
            }
            if(nv != root)
                delete nv;

            os << "\t";
        }
        else{
            if(lvQueue.empty()) 
                return ;
            else{
                lvQueue.push_back(nullptr);
            }
            os << std::endl;
        }
    }
}



Page * BtreePlus::allocPage(){
    assert(pager != nullptr);
    PageNumberType pageNo = allocator->nextPageNo();
    return pager->allocPage(pageNo);
}
void BtreePlus::freePage(Page * page){
    assert(page != nullptr);
    pager->releasePage(page); 
    allocator->free(page->getNo());
}
int BtreePlus::writePage(Page * page){
    assert(page != nullptr);
    return pager->writePage(page);
}

int BtreePlus::commit(){
    return pager->savePoint();
}





BtreePlus * BtreePlus::Create(){
    auto btrp = new BtreePlus("tbl_order_btreePlus");

    btrp->open();


    auto leftLeaf =  IBtreePlusNodeView::CreateLeaf(btrp->allocPage());
    leftLeaf->append(1, "hello1");
    leftLeaf->append(2, "hello2");
    leftLeaf->append(3, "hello3");
    btrp->writePage(leftLeaf->getPage());
    
    auto rightLeaf = IBtreePlusNodeView::CreateLeaf(btrp->allocPage());
    rightLeaf->append(4, "hello4");
    rightLeaf->append(5, "hello5");
    rightLeaf->append(6, "hello6");
    btrp->writePage(rightLeaf->getPage());

    leftLeaf->setNext(rightLeaf->getPageNo());
    rightLeaf->setNext(0);


    assert(btrp->root != nullptr);
    auto oldRoot = btrp->root;
    auto page = btrp->pager->allocPage(oldRoot->getPageNo());
    assert(page != nullptr);
    btrp->root = IBtreePlusNodeView::CreateInterior(page);
    delete oldRoot;
    ((BtreePlusInteriorNodeView*)btrp->root)->append(1, leftLeaf->getPageNo());
    ((BtreePlusInteriorNodeView*)btrp->root)->append(4, rightLeaf->getPageNo());

    leftLeaf->setParent(btrp->root->getPage()->getNo());
    rightLeaf->setParent(btrp->root->getPage()->getNo());

    btrp->writePage(btrp->root->getPage());

    return btrp;
}


static void testCreatePrintFind(){
    auto btree = BtreePlus::Create();
    btree->commit();

    std::cout << btree->toString() << std::endl;

    std::string data;
    assert( 0 == btree->find(1, data));
    std::cout << data << std::endl;
    assert( 0 == btree->find(2, data));
    std::cout << data << std::endl;
    assert( 0 == btree->find(3, data));
    std::cout << data << std::endl;
    assert( 0 == btree->find(4, data));
    std::cout << data << std::endl;
    assert( 0 == btree->find(5, data));
    std::cout << data << std::endl;
    assert( 0 == btree->find(6, data));
    std::cout << data << std::endl;

    btree->close();
    delete btree;
}

static void testInsert(){
    auto btree = new BtreePlus("insert");
    btree->open(); //load root from Memory
    
    assert(0 == btree->insert(5, "hello5"));
    assert(0 == btree->insert(4, "hello4"));
    assert(0 == btree->insert(3, "hello3"));
    assert( 0 == btree->insert(2, "hello2"));
    assert(0 == btree->insert(1, "hello1"));
    assert(0 == btree->insert(6, "hello6"));
    assert(0 == btree->insert(0, "hello0"));
    assert(0 == btree->insert(7, "hello7"));
    assert(0 == btree->insert(8, "hello8"));
    assert(0 == btree->insert(9, "hello9"));
    assert(0 == btree->insert(10, "hello10"));
    assert(0 == btree->insert(11, "hello11"));
    assert(0 == btree->insert(12, "hello12"));
    assert(0 == btree->insert(13, "hello13"));
    assert(0 == btree->insert(14, "hello14"));
    assert(0 == btree->insert(15, "hello15"));
    assert(0 == btree->insert(16, "hello16"));
    assert(0 == btree->insert(17, "hello17"));
    assert(0 == btree->insert(18, "hello18"));
    assert(0 == btree->insert(19, "hello19"));
    assert(0 == btree->insert(20, "hello20"));
    assert(0 == btree->insert(21, "hello21"));
    assert(0 == btree->insert(22, "hello22"));
    std::cout << btree->toString() << std::endl;
    
    btree->close(); //commit to file
    delete btree;
}

void BtreePlus::test(){
    std::cout <<  "BtreePlus testing..." <<std::endl;
    testCreatePrintFind();
    testInsert();
}
